package graph;

import org.junit.Test;

import java.util.*;

/*
 *@description 蛇梯棋
 *@author hkfan
 *@version 1.0
 *@create 2025/6/20 13:46
 */
public class LeetCode_909 {

    @Test
    public void test(){
        System.out.println(snakesAndLadders(new int[][]{
                new int[]{ 1,1,-1},
                new int[]{1,1,1},
                new int[]{-1,1,1},
        }));
    }

    public int snakesAndLadders(int[][] board) {
        //1. 定义
        HashMap<Integer, Integer> map = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        int n = board.length;
        //2. 队列初始化
        queue.add(1);
        map.put(1,0);
        //3. 循环
        while (!queue.isEmpty()){
            if (map.containsKey(n*n)){
                return map.get(n*n);
            }
            Integer num = queue.poll();

            for (int k = num+1; k <= Math.min(num+6,n*n); k++) {
                int[] coordinate = getCoordinate(k, n);
                int i = coordinate[0],j=coordinate[1];
                int to = board[i][j]==-1?k:board[i][j];
                if (!map.containsKey(to)){
                    map.put(to,map.get(num)+1);
                    queue.add(to);
                }


            }
        }
        return -1;
    }

    private int[] getCoordinate(int num, int n) {
        int row = (num-1)/n;
        int col = (num-1)%n;
        if (row%2==1){
            col=n-1-col;
        }
        return new int[]{n-1-row,col};
    }

}
